#include"graph.h"

void create (AdjList **pp_ag, double g[][MAX], int v, int e)
{
	int i, j;
	(*pp_ag) = (AdjList *)malloc(sizeof(AdjList));
	(*pp_ag)->v_num = 0;
	(*pp_ag)->e_num = 0;

	for (i = 0; i < MAX; ++i)
		(*pp_ag)->vetxs[i].first_adj_edg = NULL;

	for (i = 0; i < MAX; ++i)
		for (j = MAX - 1; j >= 0; --j)
			if (g[i][j] != 0 && g[i][j] != INF)
				insert_front(*pp_ag, i, j, g[i][j]);
	(*pp_ag)->v_num = v;
	(*pp_ag)->e_num = e;
}

void insert_front (AdjList *p_ag, int i, int j, double weight)
{
	EdgNode *pNode = (EdgNode *)malloc(sizeof(EdgNode));
	pNode->vetx = j;
	pNode->weight = weight;
	
	pNode->next = p_ag->vetxs[i].first_adj_edg;
	p_ag->vetxs[i].first_adj_edg = pNode;
	
}

void print (AdjList *p_ag)
{
	int i;
	EdgNode *pNode = NULL;
	
	for (i = 0; i < p_ag->v_num; ++i) {
		printf("%d", i);
		pNode = p_ag->vetxs[i].first_adj_edg;
		while (pNode != NULL) {
			printf("  ->%d[%2.0f]", pNode->vetx, pNode->weight);
			pNode = pNode->next;
		}
		printf("  ->/\\\n");
	}
		
}

void destroy (AdjList *p_ag)
{
	int i;
	EdgNode *pNode = NULL, *pNext = NULL;
	
	for (i = 0; i < p_ag->v_num; ++i) {
		pNode = p_ag->vetxs[i].first_adj_edg;
		if (pNode != NULL) {
			pNext = pNode->next;
			while (pNext != NULL) {
				free(pNode);
				pNode = pNext;
				pNext = pNext->next;
			}
			free(pNode);
		}
	}

	free(p_ag);
}

void top_sort (AdjList *p_ag)
{
	int i, j;
	int stack[MAX], top = -1;
	EdgNode *pNode = NULL;

	for (i = 0; i < p_ag->v_num; ++i)
		p_ag->vetxs[i].count = 0;

	for (i = 0; i < p_ag->v_num; ++i) {
		pNode = p_ag->vetxs[i].first_adj_edg;
		while (pNode != NULL) {
			p_ag->vetxs[pNode->vetx].count += 1;
			pNode = pNode->next;
		}
	}

	for (i = 0; i < p_ag->v_num; ++i)
		if (p_ag->vetxs[i].count == 0)
			stack[++top] = i;
	
	printf("top sort:\n");
	while (top != -1) {
		i = stack[top--];
		printf(" %d,", i);
		
		pNode = p_ag->vetxs[i].first_adj_edg;
		while (pNode != NULL) {
			j = pNode->vetx;
			if ((--p_ag->vetxs[j].count) == 0)
				stack[++top] = j;
			pNode = pNode->next;
		}
	}
	printf("\n");
}
